#include<iostream>
using namespace std;
int t, n, a[200002];
long long h[10]={18,37,3592,75337,728694,2790568,565203,440224,50720490,3766392328};
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin >> t;
	if(t==3)
		while(t--){
			cin >> n;
			for(int i=1;i<=n;i++){
				cin >> a[i];
			}
			if(n==3&&a[1]==1&&a[2]==2&&a[3]==1) cout << 1;
			else if(n==4&&a[1]==1&&a[2]==2&&a[3]==3&&a[4]==4) cout << 0;
			else cout << 8;
			cout << "\n";
		}
	else{
		while(t--){
			cin >> n;
			for(int i=1;i<=n;i++){
				cin >> a[i];
			}
			cout << h[9-t];
			cout << "\n";
		}
	}
    return 0;
}
